Papers with greedy algorithm
A Formal Perspective on Byte-Pair Encoding (2023.findings-acl)
Copied to clipboard
| Challenge: | Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. |
| Approach: | They propose an algorithm which is a 1/sigma*(1-e(-sigma))-approximation of an optimal merge sequence. |
| Outcome: | The proposed algorithm improves the runtime complexity from O(NM) to O(N log M) and the lower bound of the approximation is approx0.37. |
The Computational Complexity of Distinctive Feature Minimization in Phonology (N18-2)
Copied to clipboard
| Challenge: | a standard assumption in phonology is that finding a minimal feature specification is an automatic part of acquisition and generalization. |
| Approach: | They analyze the problem of determining whether a set of phonemes forms a natural class and find the minimal feature specification for the class. |
| Outcome: | The proposed model is based on a greedy algorithm that fails to find minimal features . the proposed model can be used to find features that are universal across languages . |
Generating Natural Language Adversarial Examples through Probability Weighted Word Saliency (P19-1)
Copied to clipboard
| Challenge: | Existing approaches to attack text classification are limited due to the complexity of the problem. |
| Approach: | They propose a greedy algorithm to generate adversarial examples that maintain lexical correctness, grammatical correctiness and semantic similarity. |
| Outcome: | The proposed algorithm maintains lexical correctness, grammatical correctity and semantic similarity well and is hard for humans to perceive. |
Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function (N18-1)
Copied to clipboard
| Challenge: | Submodular maximization with the greedy algorithm is an effective approach to extractive summarization. |
| Approach: | They propose a submodular maximization method that is 100 to 400 times faster than existing methods for extractive summarization. |
| Outcome: | The proposed method is 100 to 400 times faster than existing method based on integer-linear-programming formulations and achieves 95%-approximation. |
TAGCOS: Task-agnostic Gradient Clustered Coreset Selection for Instruction Tuning Data (2025.findings-naacl)
Copied to clipboard
| Challenge: | Existing methods for instruction tuning are limited due to the increasing volume of instruction datasets and the increased computational costs. |
| Approach: | They propose to extract a small and highly informative subset of training samples from a large dataset that achieves comparable performance to the full dataset. |
| Outcome: | The proposed algorithm outperforms other unsupervised methods and achieves comparable performance to the full dataset. |
Data Quality Enhancement on the Basis of Diversity with Large Language Models for Text Classification: Uncovered, Difficult, and Noisy (2025.coling-main)
Copied to clipboard
| Challenge: | Existing methods for text classification based on large language models are difficult to apply directly to solve. |
| Approach: | They propose a data quality enhancement method to improve LLMs' performance in classification tasks by using a greedy algorithm to select data and then performing fine-tuning. |
| Outcome: | The proposed method improves the performance of large language models in text classification tasks and significantly improves training efficiency, saving nearly half of the training time. |
SCA: Selective Compression Attention for Efficiently Extending the Context Window of Large Language Models (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing methods to compress the KV cache of large language models are expensive and limited in their context window and cost. |
| Approach: | They propose a method to expand the context window and reduce memory footprint by compressing the KV cache of large language models. |
| Outcome: | The proposed method can reduce memory footprint and expand context window of large language models without training. |
PyrEval: An Automated Method for Summary Content Analysis (L18-1)
Copied to clipboard
| Challenge: | PyrEval automates manual summarization evaluation of abstractive summarizing systems . extractive summaries that select complete sentences have shifted in recent years . |
| Approach: | They propose a method for automatic summarization evaluation that automates the manual pyramid method by using pre-trained vectors and a greedy algorithm to evaluate the pyramid content. |
| Outcome: | The proposed method can be applied to human and machine summaries with no retraining and in excellent time. |
Automatic Engineering of Long Prompts (2024.findings-acl)
Copied to clipboard
| Challenge: | Recent research has explored automatic prompt engineering for short prompts, typically consisting of one or a few sentences. |
| Approach: | They propose an algorithm that automatically improves long prompts by combining a greedy algorithm with beam-search to enhance the effectiveness of LLM-based mutation. |
| Outcome: | The proposed algorithm achieves 9.2% accuracy gain on eight tasks in Big Bench Hard and consistent improvements on GSM8K with various models. |
Rationales for Sequential Predictions (2021.emnlp-main)
Copied to clipboard
| Challenge: | Sequence models produce accurate predictions, but their decision making processes are hard to explain. |
| Approach: | They propose an efficient algorithm to approximate sequential objective by identifying the most faithful rationales. |
| Outcome: | The proposed algorithm is best at optimizing the sequential objective and provides the most faithful rationales. |
Morpheme Induction for Emergent Language (2025.emnlp-main)
Copied to clipboard
| Challenge: | CSAR is a greedy algorithm that weights morphemes based on mutual information between forms and meanings, then removes it from the corpus and repeats the process to induce more morphs. |
| Approach: | They propose an algorithm that weights morphemes based on mutual information between forms and meanings, selects highest-weighted pair, removes it from corpus, and repeats process to induce further morphs. |
| Outcome: | The proposed algorithm makes reasonable predictions in adjacent domains. |
TrimTokenator: Towards Adaptive Visual Token Pruning for Large Multimodal Models (2026.findings-acl)
Copied to clipboard
| Challenge: | Existing token pruning methods rely on costly calibration or suboptimal importance metrics, leading to redundant retained tokens. |
| Approach: | They propose a token pruning strategy that preserves cross-modal alignment and informational diversity. |
| Outcome: | The proposed method maintains strong performance while reducing tokens by 88.9% on two models. |